pub fn min_edge_prime_num(number: u32) -> String {
    let mut side_len = 3;
    let mut prime_num = 0;
    let mut diagonal_num = 1;
    loop {
        generate_matrix(side_len, &mut prime_num, &mut diagonal_num);
        if prime_num * 100 / diagonal_num < number {
            return format!("{},{}",side_len,prime_num)
        }
        side_len += 2;
    }
}

fn generate_matrix(side_len: u64, prime_num: &mut u32, diagonal_num: &mut u32) {
    let mut mid_value = side_len * side_len - side_len + 1;
    *diagonal_num += 4;
    for _ in 0..3 {
        if miller_rabin(mid_value) {
            *prime_num += 1;
        }
        mid_value = mid_value - side_len + 1;
    }
}


const WITNESSES: &[(u64, &[u64])] = &[
    (2_046, &[2]),
    (1_373_652, &[2, 3]),
    (9_080_190, &[31, 73]),
    (25_326_000, &[2, 3, 5]),
    (4_759_123_140, &[2, 7, 61]),
    (1_112_004_669_632, &[2, 13, 23, 1662803]),
    (2_152_302_898_746, &[2, 3, 5, 7, 11]),
    (3_474_749_660_382, &[2, 3, 5, 7, 11, 13]),
    (341_550_071_728_320, &[2, 3, 5, 7, 11, 13, 17]),
    (3_825_123_056_546_413_050, &[2, 3, 5, 7, 11, 13, 17, 19, 23]),
    (u64::MAX, &[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]),
];

pub fn miller_rabin(n: u64) -> bool {
    if n % 2 == 0 { return n == 2; }
    if n == 1 { return false; }

    let mut d = n - 1;
    let mut s = 0;
    while d % 2 == 0 {
        d /= 2;
        s += 1
    }

    let witnesses =
        WITNESSES.iter().find(|&&(hi, _)| hi >= n)
            .map(|&(_, wtnss)| wtnss).unwrap();
    'next_witness: for &a in witnesses.iter() {
        let mut power = modular_pow(a, d, n);
        if power == 1 || power == n - 1 { continue 'next_witness; }

        for _ in 0..s {
            power = mod_sqr(power, n);
            if power == 1 { return false; }
            if power == n - 1 {
                continue 'next_witness;
            }
        }
        return false;
    }

    true
}

fn mod_sqr(a: u64, m: u64) -> u64 {
    (a as u128 * a as u128 % m as u128) as u64
}

fn modular_pow(base: u64, mut exp: u64, mode: u64) -> u64 {
    let mut result: u128 = 1;
    let mut base = base as u128;
    let mode = mode as u128;
    base %= mode;
    while exp > 0 {
        if exp & 1 == 1 {
            result = result * base % mode
        }
        base = base * base % mode;
        exp >>= 1;
    }
    result as u64
}